// https://leetcode.cn/problems/h-index/
// Created by ade on 2022/9/14.
// 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
//
//根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。
//
//如果 h 有多种可能的值，h 指数 是其中最大的那个。
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 暴力法
    int hIndex1(vector<int> &citations) {
        int sum = accumulate(citations.begin(), citations.end(), 0);
        int len = citations.size();
        int n = sqrt(sum);
        for (int i = n; i >= 1; i--) {
            int j = i;
            for (int k = 0; k < len; k++) {
                if (citations[k] >= i) {
                    j--;
                }
            }
            if (j <= 0) return i;
        }
        return 0;
    }

    // 6 6 6 6 6 5
    // 思路：从大到小排列，如果当前i的val值 大于等于 i+1(这里解释下为什么+1，因为从0开始的话，是第一个，就是1个1次浏览，所以每次索引需要加1) 这里画图更容易理解，当 citations[i] < i + 1 临界点产生
    int hIndex(vector<int> &citations) {
        sort(citations.rbegin(), citations.rend());
        int i = 0;
        for (i = 0; i < citations.size(); i++) {
            if (citations[i] < i + 1) return i;
        }
        return i;
    }
};


int main() {
    Solution so;
    vector<int> c = {3, 0, 6, 1, 5}; // 0 1 3 5 6
    cout << so.hIndex(c);
    return 0;
}
